<html>
<head>
<title>CS45: Lab 5</title>

<style type="text/css">
@import url("style/stylesheet_hw.css");
</style>
</head>

<body> 
<div id="Wrapper"> 
  <div id="HeadImgMed"> 
    <div id="HeaderSmall">
            <h1>CS45 Lab 5: 
<br>Implementing a Device Driver</h1>
	  </div>
	  <div class="TagLine">
           <b>Checkpoint 1: Due Monday April 14 in lab</b>
           <br><b>Checkpoint 2: Due Monday April 21 in lab</b>
           <br><b>Full Solution: Due Sunday April 27 before 11:59pm</b>
	  </div>
  </div> <!--Header image box-->
     
  <div id="Content">

You will demo checkpoints
to me during your Monday lab session.  You cannot use late days on the
checkpoints.
<ul><li>  <b>Checkpoint 1</b>: implement lkm functions for loading 
and unloading the module and implement open and ioctl on a Mailbox.
<li>  <b>Checkpoint 2</b>: implement close, and non-blocking 
read and write to a Mailbox (i.e. it is fine if write overwrites unread 
contents and read re-reads previously read contents).
</ul>

<h4>Contents:</h4>
<ul>
<li><A HREF="#intro">Problem Introduction</A>  
<li><A HREF="#start">Starting point code</A>
<li><A HREF="#details">Implementation Details</A> 
<li><A HREF="#tips">Tips for Getting Started</A> 
<li><A HREF="#links">Links</A> 
<li><A HREF="#handin">What to Hand in and Demo</A>
</ul>

<div class="TagLine" id="intro">Problem Introduction</div>

For this lab you will implement a device driver for a pseudo 
device, and write test programs to demonstrate that your driver works.
The pseudo device you will implement is called a Mailbox.
A Mailbox has a read end and a write end, like a pipe.  Processes can 
open either end.  Once open, they can read or write to it over and 
over, closing it when they are done.  Unlike a pipe, a Mailbox and 
its contents persist when one or both ends of it are closed, and multiple
processes can take turns opening, reading, writing and closing the Mailbox
to modify its contents.  
<p>
A device driver implements functions for managing a (typically) physical
device.  Every device driver is written to conform to the kernel's device 
driver interface. When the kernel receives an I/O requests on the device
it invokes the appropriate driver function to perform the I/O operation.  
Device driver functions are registered with the kernel when the driver is 
loaded into the kernel via <tt>insmod</tt>.  
<p>
You will implement a <b>character device driver</b> for 
Mailbox pseudo-devices (do not implement it as a block device).  
Your implementation should use blocking (rather than polling) for 
reads and writes that cannot be satisfied immediately.
<p>
Your Mailbox device driver will be implemented as a loadable kernel module 
(<b>lkm</b>) that can be loated into the the kernel at runtime by calling 
<tt>insmod</tt>; you do not need to modify, rebuild or reboot the kernel 
to implement, load, or run your Mailbox device driver.
<p>
User-level programs open, read, write, and close special files
in <tt>/dev</tt> to perform operations on Mailboxes.
You will create 8 special files in /dev corresponding to 4 Mailboxes.  
Odd numbered device files will be read-only, the other 4 will be 
write-only; with the 8 you will implement 4 Mailbox pseudo-devices 
(e.g. 0 is the write end and 1 is the read end of the same Mailbox).   
Devices have a major number and a minor number.  All devices with the same 
major number use the same device driver code; driver code is associated with 
/dev special files by creating /dev special files with the same major 
device number that is used to register its device driver code.  
<p>
Each Mailbox should have a buffer of 32 bytes.  A Writer process can
write up to 32 bytes before it blocks waiting for a reader process to
read data from the mailbox.  Reader processes will block if there is not
enough data in the mailbox to satisfy the read request.  You need to use
wait queues to block and unblock processes on a Mailbox.
<p>
As an example, shown in the figure below:
<ul>
<li> process Pi opens the write end of a Mailbox device and Pk 
opens the read end of the same Mailbox device.
<li> Pi writes "ABC" to the Mailbox and closes its end.  
<li> Pj then opens the write end and writes "XY".  
<li> If Pk reads two bytes from the Mailbox, it
will read "AB", and only three bytes will "remain" in the Mailbox "CXY".
<li> If Pk makes a subsequent request to read 4 bytes, Pk will read "CXY" out 
of the Mailbox, and then will block until at least one more byte has been 
written to it.  Pk does not return the result to the caller until 
all bytes of the read request have been read out of the Mailbox:
<b>a user-level call to read 4 bytes on a Mailbox doesn't return until 
all 4 bytes of the request have been read from the Mailbox</b>. In other
words, at user-level the read request blocks until the full read request 
can be satisfied, even though at kernel-level the implementation may read a 
byte and block several times in handling the single user-level read request.
</ul>

<p>
<p>
<center>
<img src="mailbox.jpg">
</center>


<div class="TagLine" id="start">Starting point code</div>

Together in lab we will do the following:
<br>
<font color="red">Note:</font> if you copied over the starting point code
in lab on Monday (step 1), grab a new copy of the starting point code
(mailbox.c had a bug that has since been fixed).
<ol>
<li>
<p>
Start by setting up a <a href="http://www.cs.swarthmore.edu/~newhall/cs45/s14/Labs/git_setup.html">git repo</a> for your lab 5 work (remember to add three
users: you, partner, and your shared cs45X user).  Then, copy over
my starting point files and add them to your repo:
<pre>
cp ~newhall/public/cs45/lab05/* .
</pre>
<ol>
<li> hello1.c: a simple loadable kernel module (lkm).  
<li> Makefile_hello1: the Makefile for building the hello1.ko lkm.
<li> testmailbox.c: starting point of a user-level test program for 
     testing your Mailbox devices.
<li> Makefile_testmailbox: a Makefile for the user-level test program
<li> mailbox.c: starting point for your mailbox implementation
<li> Makefile_mailbox: the Makefile for building the mailbox.ko lkm.
<li> mkdevs: a script to create eight mailbox device files in /dev
</ol>
<p>
<li>
You will use the <tt>cs45</tt> version of the kernel for this lab.
You can set this as the default kernel to boot on your VM by editing
the <tt>grub.cfg</tt> file: 
<pre> 
$ vi /boot/grub/grub.cfg
 set default="0"
 ...
 # later in file is the boot menu list of kernels:
 menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab4' ...
 menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab4 (recovery mode)' ...
 menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab3' ...
 menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab3 (recovery mode)' ...
 menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-cs45' ...
</pre> 
In the above list, kernel 2.6.32.44-cs45 is the 4th entry 
(counting from 0), so I'd set default to 4: 
<pre>
 set default="4" 
</pre> 
Then run sync; sync; reboot and the 2.6.32.44-cs45 kernel should be 
the default (and don't run update-grub or default will be set back to 0.)  
<p>
 Run uname -a to see that the right version of the kernel booted, and if 
not, edit grub.cfg and try again 
<p> 
<li> scp  over the starting point code onto your VM.  
<pre>
$ scp -P 10022 -r  /local/me_n_pa/lab5 swatcs@yourmachine:.  
</pre> 

<li> <h4>Try out a kernel module</h4>

To build an lkm, you must compile it on your virtual box VM (not on the 
CS machines).
As a regular user on your VM, build the hello1 module you copied over 
in the modules subdirectory: 
<pre> 
$ cp Makefile_hello1 Makefile
$ make 
$ ls 
hello1.ko   
</pre>
As sudo, try inserting and removing the hello kernel module:
<pre> 
$ sudo insmod hello1.ko    # insert the hello1 module, has printk output
$ lsmod                    # list all loaded kernel modules 
$ sudo rmmod hello1        # remove the hello1 module, has printk output 
</pre>
</ol>

<br>
<br>
<div class="TagLine" id="details">Implementation Details</div>

For this lab you will implement your device driver as an lkm.
You need to implement read, write, open, ioctl, and release (close) 
routines, as well as complete the mailbox_init and mailbox_cleanup functions 
that are called when your modules is loaded/unloaded in the kernel.
User-level processes will trigger your device 
driver code by opening, reading, writing, and closing "mailboxi" 
device files in /dev.  
See <a href="#tips">Tips for Getting Started</a> below for 
some implementation hints and suggestions.
<p>
<h4>Semantics of read, write, open close, and ioctl</h4>
<ol>
        <li> A process must open a mailbox device before it can read or 
             write to it.
        <p>
        <li> Only one process at a time can have an end of a mailbox 
             device open; there can be at most a single process with the 
             read end open and a single process with the write-end open.  
        <p>
        <li> The state of mailbox devices lives past the processes who open 
             them.  For example, if one process opens the write-end writes 
             'ABC' then closes the write-end, 'ABC' stay in the mailbox 
             until a process opens the read-end and reads 3 bytes.  A third
             process can come along and open the wite-end and write 'XYZ' that
             could be read by the process with the read-end open.   
        <p>
        <li>With each of your 4 mailbox pseudo-devices is a buffer 
            of 32 bytes.  A process that writes to one of these devices will 
            block if there is not enough space to write the data (it needs 
            to wait for a reader to read some bytes).  A process that reads 
            from the device will block if there are not enough bytes of
            for the writer to write some more bytes).
            <br> 
        You should use <b>wait queues</b> to block readers/writers that are
        waiting for bytes to read/write, and you can call <b>wake_up</b> to 
        unblock
        a reader/writer when there is something to read/write from the mailbox.  
        <p>

        <li> Reading from an empty mailbox will block the calling process 
             until there is something written to the mailbox;  a write on 
             the corresponding write mailbox device, will unblock the 
             waiting reader.  
        <p>
	<li> A close to the write-end of a mailbox  when a process is 
	waiting on the read-end of the mailbox results in the reader 
	continuing to wait (this is different from what would happen on a pipe 
	if the writer process closed its end of the pipe); the reader will 
	wait until another process comes along and opens the write end of the 
	mailbox and starts writing data (this is like producer-consumer 
	semantics for close).  Similarly, a close to a read mailbox when 
	there is a waiting writing process results in the waiter continuing 
	to block (it will wait for the next reader to open the read mailbox 
	and start reading).
        <p>
	<li> A call by a user-level program to read/write X bytes from/to 
        a mailbox should not return until all X bytes have been read 
        from/written to the mailbox (unless an error occurs).
        <p>
	<li> Your ioctl function should print mailbox information using printk.
	You can use this to debug and to demo your solution.  Some things you
        should print out:
        <ol>
          <li> the buffer contents of the 4 mailboxes
          <li> the read and write offsets for each mailbox
          <li> the number of bytes currently stored in each mailbox
          <li> information about which process has mailbox endpoints open
        </ol>
        You can add any additional output you want, but keep it fairly 
        concise and easy to read.  For example, you could print out 
        each Mailbox's contents like this:
<pre>
Mailbox Contents:                      
0: abcdexxxxxxxxxxAAAAAAAAAAAAAAAAA    
1: ssssssssssssssssssssrrrrrrrrrrrr      
2: aa345679aaaaaaaaaaaaaaaaaaaaaaaa
3: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
</pre>
        Remember that the mailbox buffers are just arrays of char values, 
        so you cannot print out the contents as a string (there is no 
        terminating '\0'), instead you have to print out each char one 
        at a time.
        <p>
        Also, remember that you cannot call ioctl without a valid file 
        descriptor...your process has to have at least one mailbox open
        and use its file descriptor to pass to ioctl to get it to print
        out mailbox information.
</ol>

<h4>Loadable Kernel Modules and Character Device Drivers</h4>


<ul>
<li> A Mailbox lkm has 2 parts: 
<ol>
<li> The device driver part that implements functions that are
     called on opening, closing, reading, writing or ioctling a
     mailbox device. 
<li> The lkm initialization and cleanup parts that are invoked on
     insmod and rmmod.  Initialize global state in the init funciton,
     and clean-up any necessary state in the cleanup function.
</ol>
<li> <b>registering a device driver:</b>The mailbox_init function in the 
starting point shows an example of how to register a device driver on one 
of the 8 device files you need to create.  Part of registering a device driver
includes defining a set of functions that are registered with the Virtual 
File System (VFS); each VFS inode has a set of file operations for 
the file system object to which it points.  These functions are called 
when a user-level program makes an I/O system call (ex. read or write) on 
one of your /dev/mailbox devices. 
<p>
<li> As sudo, run <tt>insmod</tt> to load your lkm, <tt>rmmod</tt>
to unload it, and <tt>lsmod</tt> to list all kernel modules.  
In the starting point code <tt>insmod</tt> will invoke <tt>mailbox_init</tt>.
<p>
<li>The <tt>rmmod</tt> command invokes 
<tt>mailbox_cleanup</tt> that unloads your device driver
code from the kernel and unregisters the drivers from the mailbox
devices by calling <tt>cdev_del</tt>.
<p>
<tt>rmmod</tt> should not succeeded unless all
mailbox devices are closed.  
<p>
note: rmmod is a bit flaky, so if it fails you will need to reboot
the kernel to remove your lkm.
<p>
<li> You will likely need to included the following headers in your lkm:
<pre>
 linux/kernel.h	
 linux/module.h	  # lkm types/function prototypes 
 linux/init.h     # some useful macros
 linux/fs.h       # file_operations type for device driver
 linux/wait.h     # wait queue types/function prototypes
 linux/list.h     # list types/function prototypes
 asm/uaccess.h    # useful functions 
 linux/cdev.h     # character device interface functions
 asm/current.h    
 linux/sched.h
</pre>
<li>To ensure that your names do not conflict 
with existing kernel symbols, declare things static as much as possible,
and use a unique prefix (like mailbox_) on functions and global variables.  
You can also search the 
<a href="http://web.cs.swarthmore.edu/lxr/source">Linux cross reference</a>
for names to see if there are any names in the kernel that could conflict
with any you add.
</ul>


<p>
<h4>Mailbox Device files</h4>


<ul>
<p>
<li> To use a mailbox device, a user level process will open, 
read, write, and close special files in /dev.  
You will create 8 special files in /dev/.  Odd numbered device files will be 
the read end of a mailbox, and even numbered device files will be the
write end of a mailbox. With the 8 device files you will implement 4 
mailbox pseudo-devices;  if the write end of a mailbox is i, then the 
corresponding read end of the mailbox is i+1.  Name your devices 
"mailboxi" where "i" is one of {0, 7}.   Use 166 as the major device 
number and {0,7} as the minor device numbers.   A list of in-use 
device numbers is in /proc/devices.  166 should be free, but if for some
reason it is not, pick a different number. 
<p>
With the starting point code is a script, mkdevs, that will create all
the device files in /dev.  Run this script as sudo after each reboot.
Here is what the script looks like:
<pre>
mknod  --mode=666 /dev/mailbox0 c 166 0
mknod  --mode=666 /dev/mailbox1 c 166 1
mknod  --mode=666 /dev/mailbox2 c 166 2
mknod  --mode=666 /dev/mailbox3 c 166 3
mknod  --mode=666 /dev/mailbox4 c 166 4
mknod  --mode=666 /dev/mailbox5 c 166 5
mknod  --mode=666 /dev/mailbox6 c 166 6
mknod  --mode=666 /dev/mailbox7 c 166 7
ls -l /dev/mail*
</pre>
The script creates device files in /dev/. At reboot, these files are removed.
You can add to the file /etc/rc.local the 8 mknod commands above, and then
on re-boot the mailbox device files will be re-created "automatically".
<p>
If you do ls -l on these files, you will see information for the device:
<pre>
#    file_permission  device_file_name          char_dev   major# minor#
mknod --mode=666     /dev/mailbox7                   c      166       7
</pre>
<p>



<li>To print the device major and minor number from the file's inode:
<pre>
    printk("Device %d:%d\n",inode-&gt;i_rdev &gt;&gt; 8, inode-&gt;i_rdev &amp; 0xff);
</pre>
</ul>
<p>
<h4>User-level test program</h4>
Implement a simple <b>menu-driven</b> program for testing your Mailboxes
(similar to what you did in lab 3).  
<p>
User-level test code should use 
the system calls <tt>open</tt>, <tt>close</tt>, <tt>read</tt>, <tt>write</tt>, and <tt>ioctl</tt> on <tt>/dev/mailboxX</tt> files
for manipulating Mailboxes.
<p>
<b>Do not use</b> FILE *, fopen, fread, etc.
<br>
<br>
<div class="TagLine" id="tips">Tips for getting started</div>
<table width="100%" border=1>
<tr>
<td>
<center><font color="red"><b>REMEMBER:</b></font> </center>
</td>
</tr>
<tr>
<td>
<ul>
<li>You will be doing most of your
code development on the virtualbox VM.  Be sure to periodically scp 
your code back to the git repo on a CS machine and commit and push it
so that you don't lose your work.  
<li>Also, you need to re-run the mkdevs script after each reboot to 
recreate the 8 /dev mailbox files.
</ul>
</td>
</tr>
</table>
<ol>
<li> After reading through on-line lkm and device driver documentation, start 
by loading and unloading the hello lkm, to get an idea
of what insmod, lsmod, and rmmod does.
<li> Next, create the mailbox device files and try loading and unloading
the staring point lkm.
<li> Next, implement open, iotcl and close on a mailbox device
Add to your user-level test program a call to open one of your 
files in /dev and see what happens.
<li> Next add support for non-blocking read to a mailbox device.  Just
initialize the mailbox with 32 bytes of some string and have the reader
read bytes from this "static" 32 byte string (i.e. if read is for 40 bytes
and the static mailbox string is "abcd...z123456", then have the read 
return "abcd...z123456abcdef").
<li>
Next, add support for a non-blocking <tt>write</tt> to a mailbox; the
write may overwrite bytes not yet read by the reader process. 
<li> At this point, it would be good to add support for all error conditions
that do not have to do with processes blocking, and test that your error
handling code. 
<li> Next add support for blocking reader and writer processes.  A writer 
process will block when the mailbox buffer fills and the write cannot 
complete until a reader reads some bytes out of the buffer (the writer must 
wait until the reader has read bytes rather than just writing over them).  A
reader process blocks when it tries to read more bytes from the mailbox than
there are bytes to read (the reader must wait for the writer process to write
more).  Your solution should allow readers and writers to make read and write 
requests that are much larger than the mailbox buffer size.  In this case 
a reader or writer process may block and unblock multiple times before the 
single read or write request is complete (i.e. a user level call to 
read 2000 bytes on a mailbox doesn't return until all 2000 bytes have been 
read even though in your kernel-level implementation of read, the process 
will block and unblock many times while reading this many bytes).  
You may want to first implement and test blocking readers
then implement and test blocking writers.  
<li> Finally, make sure that your code is robust.  Think about error 
conditions that you will need to test (this is not a complete list):  
what happens when a process tries to read, write, open a 
mailbox device opened by another process? what happens
if a process tries to write to the read end of a mailbox or tries to 
open the read end for writing?  what happens if a reader processes 
is blocked on a mailbox and the writer process closes it or exits?
</ol>

<br>
<br>
<div class="TagLine" id="links">Resources</div>

There are some on-line references for device drivers and lkms.  Keep in 
mind that these interfaces change a fair amount, so some of the details may
differ in the kernel version we are using.
<ul>
<li> 
<a href="http://www.tldp.org/LDP/lkmpg/2.6/html/index.html">Linux Kernel Module 
	Programming Guide by Salzman, Burian, Pomerantz</a>. 
Keep in mind that there are some differences between the version of 
the kernel we are using and the older version described here.
<li> 
<a href="http://lwn.net/Kernel/LDD3/">Linux Device Drivers, Third Edition</a>,
by Corbet, Rubini, and Kroah-Hartman.  Chapter 3 is likely most useful for
this assignment.
<p>
Also, refer to struct defs and function prototypes in version 2.6.32.44 of the linux,
as some types may differ from the version of linux used in this documentation.
</ul>

<br>
<br>
<div class="TagLine" id="handin">Submit</div>
<p>
You will submit a single tar file containing
your lab 5 solution and submit it via
<a href="../../howto_runninghandin.html">cs45handin</a>
<b>Only one of you or your partner should submit your tar file 
via cs45handin</b>. If you accidentally both submit it, send me email 
right away letting me know which of the two solutions I should keep and 
which I should discard.
You can run cs45handin as many times as you like, and only the
most recent submission will be recorded. 

<p>
Your lab5 tar file should include the following 
(see <a href="http://www.cs.swarthmore.edu/~newhall/unixlinks.html#tools">
Unix Tools</a> for more information on script, dos2unix, make, and tar):
<p>
<ol>
<li> README file containing the following information:
  <ol>
  <li> Your name and your partner's name
  <li> The number of late days you used on this assignment
  <li> The number of late days you have used so far
  <li> Information telling me how to build, load, and run your device
       driver code and your test program(s).
  </ol>
<p>
<li> Copies of the test program(s) you wrote including Makefile(s).  Your
     test program(s) should be well commented and include descriptions the 
     functionality that you are testing at different points in your program, 
     and include descriptions of how to run your test program.  
<p>
<li> Copies of all source files, header files and makefiles that I 
     need to compile, load, run and test your mailbox device driver.
     Again, this should be well commented code.
</ol>
<p>
<p>
<h3>Demo</h3>
After submitting your lab, you and your partner will sign-up for a 
30 minute demo slot.  You should demonstrate that your device driver
is correct and robust.  I will definitely want to see how you handle 
reader and writer blocking.  Make sure that your ioctl function prints
out enough information about mailboxes for your to "show me" the effects
after open, close, read and write operations.  If it doesn't, then add
some more output to your ioctl or some debug printks to functions so
that you can more easily demonstrate that 
your code works. 


</div> <!--content--> 
<div id="Footer">
<p>
<!--Common footer text/images-->
<br>
<small>
<!--File/php last-edited time stamping-->
Last updated: Monday, April 14, 2014 at 04:34:10 PM</small>
</div>
</div> <!--wrapper-->
</body>
</html>
